package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.ListNode;
import com.xyhuo.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 有序链表转换二叉搜索树
 * https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/
 *
 * @time 2024/1/9
 */
public class SortedListToBST {

    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = toList(head);
        return search(list, 0, list.size() - 1);
    }

    private List<Integer> toList(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null) {
            nums.add(tmp.val);
            tmp = tmp.next;
        }
        return nums;
    }

    private TreeNode search(List<Integer> nums, int left, int right) {
        if (left > right || left < 0 || right >= nums.size()) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums.get(left));
        }
        int middle = (right - left) / 2;
        TreeNode root = new TreeNode(nums.get(left + middle));
        root.left = search(nums, left, left + middle - 1);
        root.right = search(nums, left + middle + 1, right);
        return root;
    }
}
